Collections Framework

Introduction

There are several data structures known in the field of Computer Science, which are shown in Fig. 3.1. All the data structures can be broadly classified into two categories, namely linear and non-linear data structures. Linear data structures include: array, linked list, stack and queue. Further, the linear data structures can be classified as indexed and sequential. For example, array is an indexed data structures whereas, linked list is a sequential data structures. Stack and queue can be realized as indexed and as well as sequential data structures.

Figure 3.1: Data structures

All the data structures as mentioned in Figure 3.1 are called basic data structures and other any complex data structures can be realized with them. Since, data structures are important to build any software system (because together algorithm and data structures are used to develop programs), Java developer elegantly supports a good library of built-in data structures utilities. In Java a concept has been introduced called collection. A collection in Java is a group of objects (of any type). The java.util package contains one of Java’s most powerful subsystems called collections framework and defined in java.utl package. The package is a huge collection of interfaces and classes that provide state-of-the-art technology for managing groups of objects. It is very popular among the programmers and software practitioners.

Why Collections framework?

The Java Collections Framework (popularly abbreviated as JVF) has been introduced to meet several goals. Some of the major goals are listed in the following.

1. The framework provides high-performance software coding. The implementations for the fundamental collections (dynamic arrays, linked lists, trees, and hash tables) are highly efficient. You seldom, if ever, need to code one of these “data engines” manually.

2. The framework allows different types of collections to work in a similar manner and with a high degree of interoperability.

3. Extending and/or adapting a collection is easy and flexible.

The entire JCF consists of two parts: Collections are under Collection and Faicities under Map framework (also see Figure 3.2). All regular data structures under linear type and set are under Collection class, whereas Tree and tables are under Map framework. Note that there is no explicit facility for graph data structure.

The hierarchy of the two compositions in Java, which are under the part of java.utility package is shown in Fig. 3.3 and Fig. 3.4, respectively.

Figure 3.2: Categorization of JCF

Figure 3.3: Hierarchy of interfaces and classes under Collection

Figure 3.4: Hierarchy of JCF’s Map

Java Legacy Classes and Interfaces

The java.util package was first time introduced in Java 2 release and becomes a more powerful subsystem for a programmer today. Prior to the release of Java 2, Java supported ad hoc classes such as Dictionary, Vector, Stack, and Properties to manipulate collection of objects. With the inclusion of the Java collection framework, several of the original classes were reengineered to support the collection interface. In other words, none of the old classes have been deprecated, rather, they are still fully compatible with the Java Collection framework and there is still code that use them. Such classes are called legacy classes. The Java’s legacy classes are shown in Fig. 3.5. There is one legacy interface called Enumeration.

Figure 3.5: Java’s legacy classes

Collection Framework

The entire Java Collections Framework (JJF) is built upon a set of standard interfaces, classes and algorithms. The hierarchy of the classes and interfaces in JCF is quite complex. A part of the JCFs is shown in Figure 3.1.

The interfaces in JCF

The core interfaces which are there in JCF is shown in Table 1. A brief description of each is given below.

Interface	Description
Collection	Enables you to work with groups of objects; it is at the top of the collections hierarchy.
List	List Extends Collection to handle sequences (lists of objects).
Queue	Queue Extends Collection to handle special types of lists in which elements are removed only from the head.
Deque	Deque Extends Queue to handle a double-ended queue
Set	Extends Collection to handle sets, which must contain unique elements.
SortedSet	Extends Set to handle sorted sets.
NavigableSet	NavigableSet Extends SortedSet to handle retrieval of elements based on closest-match

Table 3.1: Interfaces in Collections framework

The Collection interfaces

The Collection interface is the foundation upon which the Collections framework is built because it must be implemented by any class that defines a collection. Collection is a generic interface that has this declaration:

interface Collection<T>

Here, T specifies the type of objects that the collection will hold. Collection declares the core methods that all collections will have. These methods are summarized in Table 2. Because all collections implement Collection, familiarity with its methods is necessary for a clear understanding of the framework.

Method	Description
boolean add(T obj)	Adds obj to the invoking collection. Returns true if obj was added to the collection. Returns false if obj is already a member of the collection and the collection does not allow duplicates.
boolean addAll(Collection<? extends T> c)	Adds all the elements of c to the invoking collection. Returns true if the collection changed (i.e., the elements were added). Otherwise, returns false.
void clear( )	Removes all elements from the invoking collection.
boolean contains(Object obj)	Returns true if obj is an element of the invoking collection. Otherwise, returns false.
boolean containsAll(Collection<?> c)	Returns true if the invoking collection contains all elements of c. Otherwise, returns false.
boolean equals(Object obj)	Returns true if the invoking collection and obj are equal. Otherwise, returns false.
int hashCode( )	Returns the hash code for the invoking collection.
boolean isEmpty( )	Returns true if the invoking collection is empty. Otherwise, returns false.
Iterator<T> iterator( )	Returns an iterator for the invoking collection.
default Stream<E> parallelStream( )	Returns a stream that uses the invoking collection as its source for elements. If possible, the stream supports parallel operations.
boolean remove(Object obj)	Removes one instance of obj from the invoking collection. Returns true if the element was removed. Otherwise, returns false.
boolean removeAll(Collection<?> c)	Removes all elements of c from the invoking collection. Returns true if the collection changed (i.e., elements were removed). Otherwise, returns false.
default boolean removeIf( Predicate <? super T> p)	Removes from the invoking collection those elements that satisfy the condition specified by predicate.
boolean retainAll(Collection<?> c)	Removes all elements from the invoking collection except those in c. Returns true if the collection changed (i.e., elements were removed). Otherwise, returns false.
int size( )	Returns the number of elements held in the invoking collection.
default Spliterator<E> spliterator( )	Returns a spliterator to the invoking collections.
default Stream<E> stream( )	Returns a stream that uses the invoking collection as its source for elements. The stream is sequential.
Object[ ] toArray( )	Returns an array that contains all the elements stored in the invoking collection. The array elements are copies of the collection elements.
<T> T[ ] toArray(T array[ ])	Returns an array that contains the elements of the invoking collection. The array elements are copies of the collection elements. If the size of array equals the number of elements, these are returned in array. If the size of array is less than the number of elements, a new array of the necessary size is allocated and returned. If the size of array is greater than the number of elements, the array element following the last collection element is set to null and an error is reported.

Table 3.2: The methods declared in Collection interface

The List interface

The List interface extends Collection and declares the behavior of a collection that stores a sequence of elements. Elements can be inserted or accessed by their position in the list, using a zero-based index. A list may contain duplicate elements. List is a generic interface that has this declaration:

interface List<T>

Here, T specifies the type of objects that the list will hold.

In addition to the methods defined by Collection, List defines some of its own, which are summarized in Table 3.3.

Method	Description
void add(int index, E obj)	Inserts obj into the invoking list at the index passed in index. Any preexisting elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten.
boolean addAll(int index, Collection<? extends E> c)	Inserts all elements of c into the invoking list at the index passed in index. Any preexisting elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten. Returns true if the invoking list changes and returns false otherwise.
E get(int index)	Returns the object stored at the specified index within the invoking collection.
int indexOf(Object obj)	Returns the index of the first instance of obj in the invoking list. If obj is not an element of the list, –1 is returned.
int lastIndexOf(Object obj)	Returns the index of the last instance of obj in the invoking list. If obj is not an element of the list, –1 is returned.
ListIterator<E> listIterator( )	Returns an iterator to the start of the invoking list.
ListIterator<E> listIterator(int index)	Returns an iterator to the invoking list that begins at the specified index.
E remove(int index)	Removes the element at position index from the invoking list and returns the deleted element. The resulting list is compacted. That is, the indexes of subsequent elements are decremented by one.
default void replaceAll(UnaryOperator<E> opToApply)	Updates each element in the list with the value obtained from the opToApply function.
E set(int index, E obj)	Assigns obj to the location specified by index within the invoking list. Returns the old value.
default void sort(Comparator<? super E> comp)	Sorts the list using the comparator specified by comp.
List<E> subList(int start, int end)	Returns a list that includes elements from start to end–1 in the invoking list. Elements in the returned list are also referenced by the invoking object.

Table 3.3: Method declared in the List interface

The Queue interface

The Queue interface extends Collection and declares the behavior of a queue, which is often a first-in, first-out list. However, there are types of queues in which the ordering is based upon other criteria. Queue is a generic interface that has this declaration:

interface Queue<T>

Here, T specifies the type of objects that the queue will hold. The methods declared by Queue are shown in Table 3.4.

Method	Description
Eelement( )	Returns the element at the head of the queue. The element is not removed. It throws NoSuchElementException if the queue is empty.
boolean offer(T obj)	Attempts to add obj to the queue. Returns true if obj was added and false otherwise.
T peek( )	Returns the element at the head of the queue. It returns null if the queue is empty. The element is not removed.
T poll( )	Returns the element at the head of the queue, removing the element in the process. It returns null if the queue is empty.
T remove( )	Removes the element at the head of the queue, returning the element in the process. It throws NoSuchElementException if the queue is empty.

Table 3.4: The methods declared in Queue interface

The Dequeue interface

The Deque interface extends Queue and declares the behavior of a double-ended queue. Double-ended queues can function as standard, first-in, first-out queues or as last-in, firstout stacks. Deque is a generic interface that has this declaration:

interface Deque<T>

Here, T specifies the type of objects that the deque will hold. In addition to the methods that it inherits from Queue, Deque adds those methods summarized in Table 3.5.

Method	Description
void addFirst(E obj)	Adds obj to the head of the deque. Throws an IllegalStateException if a capacity-restricted deque is out of space.
void addLast(E obj)	Adds obj to the tail of the deque. Throws an IllegalStateException if a capacity-restricted deque is out of space.
Iterator<E> descendingIterator( )	Returns an iterator that moves from the tail to the head of the deque. In other words, it returns a reverse iterator.
E getFirst( )	Returns the first element in the deque. The object is not removed from the deque. It throws NoSuchElementException if the deque is empty.
E getLast( )	Returns the last element in the deque. The object is not removed from the deque. It throws NoSuchElementException if the deque is empty.
boolean offerFirst(E obj)	Attempts to add obj to the head of the deque. Returns true if obj was added and false otherwise. Therefore, this method returns false when an attempt is made to add obj to a full, capacity-restricted deque.
boolean offerLast(E obj)	Attempts to add obj to the tail of the deque. Returns true if obj was added and false otherwise.
E peekFirst( )	Returns the element at the head of the deque. It returns null if the deque is empty. The object is not removed.
E peekLast( )	Returns the element at the tail of the deque. It returns null if the deque is empty. The object is not removed.
E pollFirst( )	Returns the element at the head of the deque, removing the element in the process. It returns null if the deque is empty.
E pollLast( )	Returns the element at the tail of the deque, removing the element in the process. It returns null if the deque is empty.
E pop( )	Returns the element at the head of the deque, removing it in the process. It throws NoSuchElementException if the deque is empty.
void push(E obj)	Adds obj to the head of the deque. Throws an IllegalStateException if a capacity-restricted deque is out of space.
E removeFirst( )	Returns the element at the head of the deque, removing the element in the process. It throws NoSuchElementException if the deque is empty.
boolean removeFirstOccurrence(Object obj)	Removes the first occurrence of obj from the deque. Returns true if successful and false if the deque did not contain obj.
E removeLast( )	Returns the element at the tail of the deque, removing the element in the process. It throws NoSuchElementException if the deque is empty.
boolean removeLastOccurrence(Object obj)	Removes the last occurrence of obj from the deque. Returns true if successful and false if the deque did not contain obj.

Table 3.5: The methods declared in Deque interface

The Set interface

The Set interface defines a set. It extends Collection and specifies the behavior of a collection that does not allow duplicate elements. Therefore, the add( ) method returns false if an attempt is made to add duplicate elements to a set. It does not specify any additional methods of its own. Set is a generic interface that has this declaration:

interface Set<T>

Here, T specifies the type of objects that the set will hold.

The SortedSet interface

The SortedSet interface extends Set and declares the behavior of a set sorted in ascending order. SortedSet is a generic interface that has this declaration:

interface SortedSet<T>

Here, T specifies the type of objects that the set will hold.

In addition to those methods provided by Set, the SortedSet interface declares the methods summarized in Table 3.6.

Method	Description
Comparator<? super E> comparator( )	Returns the invoking sorted set’s comparator. If the natural ordering is used for this set, null is returned.
E first( )	Returns the first element in the invoking sorted set.
SortedSet<E> headSet(E end)	Returns a SortedSet containing those elements less than end that are contained in the invoking sorted set. Elements in the returned sorted set are also referenced by the invoking sorted set.
E last( )	Returns the last element in the invoking sorted set.
SortedSet<E> subSet(E start, E end)	Returns a SortedSet that includes those elements between start and end–1. Elements in the returned collection are also referenced by the invoking object.
SortedSet<E> tailSet(E start)	Returns a SortedSet that contains those elements greater than or equal to start that are contained in the sorted set. Elements in the returned set are also referenced by the invoking object.

Table 3.6: The methods in SortedSet interface

The NavigableSet interface

The NavigableSet interface extends SortedSet and declares the behavior of a collection that supports the retrieval of elements based on the closest match to a given value or values. NavigableSet is a generic interface that has this declaration:

interface NavigableSet<T>

Here, T specifies the type of objects that the set will hold. In addition to the methods that it inherits from SortedSet, NavigableSet adds those summarized in Table 3.7.

Method	Description
E ceiling(E obj)	Searches the set for the smallest element e such that e >= obj. If such an element is found, it is returned. Otherwise, null is returned.
Iterator<E> descendingIterator( )	Returns an iterator that moves from the greatest to least. In other words, it returns a reverse iterator.
NavigableSet<E> descendingSet( )	Returns a NavigableSet that is the reverse of the invoking set. The resulting set is backed by the invoking set.
E floor(E obj)	Searches the set for the largest element e such that e <= obj. If such an element is found, it is returned. Otherwise, null is returned.
NavigableSet<E> headSet(E upperBound, boolean incl)	Returns a NavigableSet that includes all elements from the invoking set that are less than upperBound. If incl is true, then an element equal to upperBound is included. The resulting set is backed by the invoking set.
E higher(E obj)	Searches the set for the largest element e such that e > obj. If such an element is found, it is returned. Otherwise, null is returned.
E lower(E obj)	Searches the set for the largest element e such that e < obj. If such an element is found, it is returned. Otherwise, null is returned.
E pollFirst( )	Returns the first element, removing the element in the process. Because the set is sorted, this is the element with the least value. null is returned if the set is empty.
E pollLast( )	Returns the last element, removing the element in the process. Because the set is sorted, this is the element with the greatest value. null is returned if the set is empty.
NavigableSet<E> subSet(E lowerBound, boolean lowIncl, E upperBound, boolean highIncl)	Returns a NavigableSet that includes all elements from the invoking set that are greater than lowerBound and less than upperBound. If lowIncl is true, then an element equal to lowerBound is included. If highIncl is true, then an element equal to upperBound is included. The resulting set is backed by the invoking set.
NavigableSet<E> tailSet(E lowerBound, boolean incl)	Returns a NavigableSet that includes all elements from the invoking set that are greater than lowerBound. If incl is true, then an element equal to lowerBound is included. The resulting set is backed by the invoking set.

Table 3.7: The NavigableSet interface

The Collection classes

As you know interfaces are design rule, that is, it is the programmer task to have the implementations of each and every interfaces. It seems, then how the java.util package is useful. In fact, here, we are going to learn about the Collection classes. The Collection classes are the collection of classes which implements the interfaces we have discussed. In addition, the collection classes include many abstract classes as well. Anyway, a programmer has full liberty to adopt the implemented collection classes in their programs or they can implement of their own. The core collection classes are listed in Table 3.8.

Class	Description
AbstractCollection	Implements most of the Collection interface.
AbstractList	Extends AbstractCollection and implements most of the List interface.
AbstractQueue	Extends AbstractCollection and implements parts of the Queue interface.
AbstractSequentialList	Extends AbstractList for use by a collection that uses sequential rather than random access of its elements.
LinkedList	Implements a linked list by extending AbstractSequentialList.
ArrayList	Implements a dynamic array by extending AbstractList.
ArrayDeque	Implements a dynamic double-ended queue by extending AbstractCollection and implementing the Deque interface.
AbstractSet	Extends AbstractCollection and implements most of the Set interface.
EnumSet	Extends AbstractSet for use with enum elements.
HashSet	Extends AbstractSet for use with a hash table.
LinkedHashSet	Extends HashSet to allow insertion-order iterations.
PriorityQueue	Extends AbstractQueue to support a priority-based queue.
TreeSet	Implements a set stored in a tree. Extends AbstractSet.

Table 3.8: The core collection classes in the Collection Framework

Data Structures using JCF

You will learn how the different data structure that you can implement in your programs using the utilty available in java,uti package. Overall, all the data structures can be broadly classified into four categories. The brad data structures classification is shown in Table 3.9.

Data Structures	List	Queue	Set	Map
Indexed	ArrayList	ArrayDeque	HashSet	HashMap
Sequential	LinkedList	PriorityQueue	TreeSet	TreeMap
Indexed with links			LinkedHashSet	LinkedHashMap
Bit string			EnumSet	EnuMap

Table 3.9: Different data structures using Java Collection Framework

The Legacy Classes and Interfaces

Early version of java did not include the Collections framework. It only defined several classes and interfaces that provide methods for storing objects. +
When Collections framework were added in J2SE 1.2, the original classes were reengineered to support the collection interface. These classes are also known as Legacy classes.
All legacy classes and interface were redesign by JDK 5 to support Generics.
The legacy classes are supported because there is still some code that uses them.

The Java’s legacy classes are shown in Fig. 3.6. There is one legacy interface called Enumeration. In the following, the interface and all legacy classes are discussed in brief.

Figure 3.6: Java’s legacy classes

Note: There is one legacy interface called Enumeration.

Enumeration Interface

Enumeration interface defines method to enumerate (obtain one at a time) through collection of objects.
This interface is superseded (replaced) by Iterator interface.
However, some legacy classes such as Vector and Properties defines several method in which Enumeration interface is used.

It has this declaration:

interface Enumeration<E>

where E specifies the type of element being enumerated.

Table 3.10: The Method by Enumeration Interface

Method

Description

boolean hasMoreElements()

It returns true while there are still more elements to extract,

and returns false when all the elements have been enumerated.

Object nextElement()

It returns the next object in the enumeration i.e. each call to nextElement() method obtains the next object in the enumeration. It throws NoSuchElementException when the enumeration is complete.

Class Vector

Vector is similar to ArrayList which represents a dynamic array.
There are two differences between Vector and ArrayList. First, Vector is synchronized while ArrayList is not, and Second, it contains many legacy methods that are not part of the Collections Framework.
With the release of JDK 5, Vector also implements Iterable. This means that Vector is fully compatible with collections, and a Vector can have its contents iterated by the for-each loop.

Vector is declared like this:

class Vector<E>

Here, E specifies the type of element that will be stored.

Table 3.11: The Constructors of Vector

Constructor	Description
Vector()	This creates a default vector, which has an initial size of 10.
Vector(int size)	This creates a vector whose initial capacity is specified by size.
Vector(int size, int incr)	This creates a vector whose initial capacity is specified by size and whose increment is specified by incr. The increment specifies the number of elements to allocate each timewhen a vector is resized for addition of objects.
Vector(Collection c)	This creates a vector that contains the elements of collection c.

Table 3.12: The Legacy Methods Defined by Vector

Method	Description
void addElement(E element)	The object specified by element is added to the vector.
int capacity( )	Returns the capacity of the vector.
Object clone( )	Returns a duplicate of the invoking vector.
boolean contains(Object element)	Returns true if element is contained by the vector, and returns false if it is not.
void copyInto(Object array[ ])	The elements contained in the invoking vector are copied into the array specified by array.
E elementAt(int index)	Returns the element at the location specified by index.
Enumeration<E> elements( )	Returns an enumeration of the elements in the vector.
void ensureCapacity(int size)	Sets the minimum capacity of the vector to size.
E firstElement( )	Returns the first element in the vector.
int indexOf(Object element)	Returns the index of the first occurrence of element. If the object is not in the vector, –1 is returned.
int indexOf(Object element, int start)	Returns the index of the first occurrence of element at or after start. If the object is not in that portion of the vector, –1 is returned.
void insertElementAt(E element, int index)	Adds element to the vector at the location specified by index.
boolean isEmpty( )	Returns true if the vector is empty, and returns false if it contains one or more elements.
E lastElement( )	Returns the last element in the vector.
int lastIndexOf(Object element)	Returns the index of the last occurrence of element. If the object is not in the vector, –1 is returned.
int lastIndexOf(Object element, int start)	Returns the index of the last occurrence of element before start. If the object is not in that portion of the vector, –1 is returned.
void removeAllElements( )	Empties the vector. After this method executes, the size of the vector is zero.
boolean removeElement(Object element)	Removes element from the vector. If more than one instance of the specified object exists in the vector, then it is the first one that is removed. Returns true if successful and false if the object is not found.
void removeElementAt(int index)	Removes the element at the location specified by index.
void setElementAt(E element, int index)	The location specified by index is assigned element.
void setSize(int size)	Sets the number of elements in the vector to size. If the new size is less than the old size, elements are lost. If the new size is larger than the old size, null elements are added.
int size( )	Returns the number of elements currently in the vector.
String toString( )	Returns the string equivalent of the vector.
void trimToSize( )	Sets the vector’s capacity equal to the number of elements that it currently holds.

Example 3.1:

The following program uses a vector to store various types of numeric objects. It demonstrates several of the legacy methods defined by Vector. It also demonstrates the Enumeration interface.

// Demonstrate various Vector operations.

import java.util.*;

class VectorDemo {

public static void main(String args[]) {

// initial size is 3, increment is 2

Vector<Integer> v = new Vector<Integer>(3, 2);

System.out.println("Initial size: " + v.size());

System.out.println("Initial capacity: " +

v.capacity());

v.addElement(1);

v.addElement(2);

v.addElement(3);

v.addElement(4);

System.out.println("Capacity after four additions: " +

v.capacity());

v.addElement(5);

System.out.println("Current capacity: " +

v.capacity());

v.addElement(6);

v.addElement(7);

System.out.println("Current capacity: " +

v.capacity());

v.addElement(9);

v.addElement(10);

System.out.println("Current capacity: " +

v.capacity());

v.addElement(11);

v.addElement(12);

System.out.println("First element: " + v.firstElement());

System.out.println("Last element: " + v.lastElement());

if(v.contains(3))

System.out.println("Vector contains 3.");

// Enumerate the elements in the vector.

Enumeration<Integer> vEnum = v.elements();

System.out.println("\nElements in vector:");

while(vEnum.hasMoreElements())

System.out.print(vEnum.nextElement() + " ");

System.out.println();

}

The output from this program is shown here:

Initial size: 0

Initial capacity: 3

Capacity after four additions: 5

Current capacity: 5

Current capacity: 7

Current capacity: 9

First element: 1

Last element: 12

Vector contains 3.

Elements in vector:

1 2 3 4 5 6 7 9 10 11 12

Example 3.2:

Example showing process of inserting some elements into a vector

import java.util.*;

public class Test{

public static void main(String[] args) {

Vector<Integer> ve = new Vector<Integer>();

ve.add(1);

ve.add(2);

ve.add(3);

ve.add(4);

ve.add(5);

ve.add(6);

Enumeration<Integer> en = ve.elements();

while(en.hasMoreElements()) {

System.out.println(en.nextElement());

}

The output from this program is shown here:

Class Stack

Stack is a subclass of Vector that implements a standard last-in, first-out stack.
Stack only defines the default constructor, which creates an empty stack.
It follows last-in, first-out principle for the stack elements.

With the release of JDK 5, Stack was retrofitted for generics and is declared as shown here:

class Stack<E>

Here, E specifies the type of element stored in the stack.

Table 3.13: The Constructors of Stack

Constructor	Description
Stack()	This creates an empty stack

Stack includes all the methods defined by Vector and adds several of its own, shown in

Table 3.14 below.

Table 3.14: The Methods Defined by Stack

Method	Description
boolean empty( )	Returns true if the stack is empty, and returns false if the stack contains elements.
E peek( )	Returns the element on the top of the stack, but does not remove it.
E pop( )	Returns the element on the top of the stack, removing it in the process.
E push(E element)	Pushes element onto the stack. element is also returned.
int search(Object element)	Searches for element in the stack. If found, its offset from the top of the stack is returned. Otherwise, –1 is returned.

Example 3.3:

To put an object on the top of the stack, call push( ). To remove and return the top element, call pop( ). You can use peek( ) to return, but not remove, the top object. An EmptyStackException is thrown if you call pop( ) or peek( ) when the invoking stack is empty. The empty( ) method returns true if nothing is on the stack. The search( ) method determines whether an object exists on the stack and returns the number of pops that are required to bring it to the top of the stack. Here is an example that creates a stack, pushes several Integer objects onto it, and then pops them off again:

// Demonstrate the Stack class.

import java.util.*;

class StackDemo {

static void showpush(Stack<Integer> st, int a) {

st.push(a);

System.out.println("push(" + a + ")");

System.out.println("stack: " + st);

}

static void showpop(Stack<Integer> st) {

System.out.print("pop -> ");

Integer a = st.pop();

System.out.println(a);

System.out.println("stack: " + st);

}

public static void main(String args[]) {

Stack<Integer> st = new Stack<Integer>();

System.out.println("stack: " + st);

showpush(st, 42);

showpush(st, 66);

showpush(st, 99);

showpop(st);

try {

showpop(st);

} catch (EmptyStackException e) {

System.out.println("empty stack");

}

The following is the output produced by the program; notice how the exception handler for EmptyStackException is caught so that you can gracefully handle a stack underflow:

stack: [ ]

push(42)

stack: [42]

push(66)

stack: [42, 66]

push(99)

stack: [42, 66, 99]

pop -> 99

stack: [42, 66]

pop -> 66

stack: [42]

pop -> 42

stack: [ ]

pop -> empty stack

Note: although Stack is not deprecated, ArrayDeque is a better choice.

Example 3.4:

Demonstrate the working of stack.

import java.util.*;

class StackDemo {

public static void main(String args[]) {

Stack st = new Stack();

st.push(1);

st.push(2);

st.push(3);

st.push(4);

st.push(5);

Enumeration e1 = st.elements();

while(e1.hasMoreElements())

System.out.print(e1.nextElement()+" ");

st.pop();

System.out.println("\nAfter popping out two elements");

Enumeration e2 = st.elements();

while(e2.hasMoreElements())

System.out.print(e2.nextElement()+" ");

}

The following is the output produced by the program:

1 2 3 4 5

After popping out two elements

1 2 3

Class Dictionary

Dictionary is an abstract class.
It represents a key/value pair and operates much like Map.
Although it is not currently deprecated, Dictionary is classified as obsolete, because it is fully superseded by Map class.

Table 3.15: The Abstract Methods Defined by Dictionary

Method	Description
Enumeration<V> elements( )	Returns an enumeration of the values contained in the dictionary.
V get(Object key)	Returns the object that contains the value associated with key. If key is not in the dictionary, a null object is returned.
boolean isEmpty( )	Returns true if the dictionary is empty, and returns false if it contains at least one key.
Enumeration<K> keys( )	Returns an enumeration of the keys contained in the dictionary.
V put(K key, V value)	Inserts a key and its value into the dictionary. Returns null if key is not already in the dictionary; returns the previous value associated with key if key is already in the dictionary.
V remove(Object key)	Removes key and its value. Returns the value associated with key. If key is not in the dictionary, a null is returned.
int size( )	Returns the number of entries in the dictionary.

Hashtable

Like HashMap, Hashtable also stores key/value pair. However neither keys nor values can be null.
There is one more difference between HashMap and Hashtable that is Hashtable is synchronized while HashMap is not.

Hashtable was made generic by JDK 5. It is declared like this:

class Hashtable<K, V>

Here, K specifies the type of keys, and V specifies the type of values.

The Hashtable constructors are shown here:

Table 3.16: The Constructors of Hashtable

Constructor	Description
Hashtable( )	This is the default constructor. The default size is 11.
Hashtable(int size)	This creates a hash table that has an initial size specified by size.
Hashtable(int size, float fillRatio)	This creates a hash table that has an initial size specified by size and a fill ratio specified by fillRatio. This ratio must be between 0.0 and 1.0, and it determines how full the hash table can be before it is resized upward. Specifically, when the number of elements is greater than the capacity of the hash table multiplied by its fill ratio, the hash table is expanded. If you do not specify a fill ratio, then 0.75 is used.
Hashtable(Map<? extends K, ? extends V> m)	This creates a hash table that is initialized with the elements in m. The capacity of the hash table is set to twice the number of elements in m. The default load factor of 0.75 is used.

Table 3.17 : The Legacy Methods Defined by Hashtable

Method	Description
void clear( )	Resets and empties the hash table.
Object clone( )	Returns a duplicate of the invoking object.
boolean contains(Object value)	Returns true if some value equal to value exists within the hash table. Returns false if the value isn’t found.
boolean containsKey(Object key)	Returns true if some key equal to key exists within the hash table. Returns false if the key isn’t found.
boolean containsValue(Object value)	Returns true if some value equal to value exists within the hash table. Returns false if the value isn’t found.
Enumeration<V> elements( )	Returns an enumeration of the values contained in the hash table.
V get(Object key)	Returns the object that contains the value associated with key. If key is not in the hash table, a null object is returned.
boolean isEmpty( )	Returns true if the hash table is empty; returns false if it contains at least one key.
Enumeration<K> keys( )	Returns an enumeration of the keys contained in the hash table.
V put(K key, V value)	Inserts a key and a value into the hash table. Returns null if key isn’t already in the hash table; returns the previous value associated with key if key is already in the hash table.
void rehash( )	Increases the size of the hash table and rehashes all of its keys.
V remove(Object key)	Removes key and its value. Returns the value associated with key. If key is not in the hash table, a null object is returned.
int size( )	Returns the number of entries in the hash table.
String toString( )	Returns the string equivalent of a hash table.

Example 3.5:

The following example reworks the bank account program, shown earlier, so that it uses a Hashtable to store the names of bank depositors and their current balances:

// Demonstrate a Hashtable.

import java.util.*;

class HTDemo {

public static void main(String args[]) {

Hashtable<String, Double> balance =

new Hashtable<String, Double>();

Enumeration<String> names;

String str;

double bal;

balance.put("John Doe", 3434.34);

balance.put("Tom Smith", 123.22);

balance.put("Jane Baker", 1378.00);

balance.put("Tod Hall", 99.22);

balance.put("Ralph Smith", -19.08);

// Show all balances in hashtable.

names = balance.keys();

while(names.hasMoreElements()) {

str = names.nextElement();

System.out.println(str + ": " +

balance.get(str));

}

System.out.println();

// Deposit 1,000 into John Doe's account.

bal = balance.get("John Doe");

balance.put("John Doe", bal+1000);

System.out.println("John Doe's new balance: " +

balance.get("John Doe"));

}

The output from this program is shown here:

Todd Hall: 99.22

Ralph Smith: -19.08

John Doe: 3434.34

Jane Baker: 1378.0

Tom Smith: 123.22

John Doe's new balance: 4434.34

Example 3.6:

The preceding program uses an enumeration to display the contents of balance. However, you can obtain set-views of the hash table, which permits the use of iterators. To do so, you simply use one of the collection-view methods defined by Map, such as entrySet( ) or keySet( ). For example, you can obtain a set-view of the keys and cycle through them using either an iterator or an enhanced for loop. Here is a reworked version of the program that shows this technique:

// Use iterators with a Hashtable.

import java.util.*;

class HTDemo2 {

public static void main(String args[]) {

Hashtable<String, Double> balance =

new Hashtable<String, Double>();

String str;

double bal;

balance.put("John Doe", 3434.34);

balance.put("Tom Smith", 123.22);

balance.put("Jane Baker", 1378.00);

balance.put("Tod Hall", 99.22);

balance.put("Ralph Smith", -19.08);

// Show all balances in hashtable.

// First, get a set view of the keys.

Set<String> set = balance.keySet();

// Get an iterator.

Iterator<String> itr = set.iterator();

while(itr.hasNext()) {

str = itr.next();

System.out.println(str + ": " +

balance.get(str));

}

System.out.println();

// Deposit 1,000 into John Doe's account.

bal = balance.get("John Doe");

balance.put("John Doe", bal+1000);

System.out.println("John Doe's new balance: " +

balance.get("John Doe"));

}

Example 3.7:

Simple example to put elements to HashTable and then show the inserted values.

import java.util.*;

class HashTableDemo

{

public static void main(String args[])

{

Hashtable<String,Integer> ht = new Hashtable<String,Integer>();

ht.put("a",new Integer(10));

ht.put("b",new Integer(20));

ht.put("c",new Integer(30));

ht.put("d",new Integer(40));

Set st = ht.entrySet();

Iterator itr=st.iterator();

while(itr.hasNext())

{

Map.Entry m=(Map.Entry)itr.next();

System.out.println(itr.getKey()+" "+itr.getValue());

}

The output from this program is shown here:

a 10

b 20

c 30

d 40

Class Properties

Properties class extends Hashtable class.
It is used to maintain list of value in which both key and value are String.
One advantage of Properties over Hashtable is that we can specify a default property that will be useful when no value is associated with a certain key.

Note: In both cases, the property list is empty

In Properties class, you can specify a default property that will be returned if no value is associated with a certain key.

Properties defines the following instance variable:

Properties defaults;

Table 3.18: The Constructors of Properties

Constructor	Description
Properties( )	This creates a Properties object that has no default values
Properties(Properties propDefault)	This creates an object that uses propdefault for its default values.

Table 3.19: The Methods Defined by Properties

Method	Description
String getProperty(String key)	Returns the value associated with key. A null object is returned if key is neither in the list nor in the default property list.
String getProperty(String key, String defaultProperty)	Returns the value associated with key. defaultProperty is returned if key is neither in the list nor in the default property list.
void list(PrintStream streamOut)	Sends the property list to the output stream linked to streamOut.
void list(PrintWriter streamOut)	Sends the property list to the output stream linked to streamOut.
void load(InputStream streamIn) throws IOException	Inputs a property list from the input stream linked to streamIn.
void load(Reader streamIn) throws IOException	Inputs a property list from the input stream linked to streamIn.
void loadFromXML(InputStream streamIn) throws IOException, InvalidPropertiesFormatException	Inputs a property list from an XML document linked to streamIn.
Enumeration<?> propertyNames( )	Returns an enumeration of the keys. This includes those keys found in the default property list, too.
Object setProperty(String key, String value)	Associates value with key. Returns the previous value associated with key, or returns null if no such association exists.
void store(OutputStream streamOut, String description) throws IOException	After writing the string specified by description, the property list is written to the output stream linked to streamOut.
void store(Writer streamOut, String description) throws IOException	After writing the string specified by description, the property list is written to the output stream linked to streamOut.
void storeToXML(OutputStream streamOut, String description) throws IOException	After writing the string specified by description, the property list is written to the XML document linked to streamOut.
void storeToXML(OutputStream streamOut, String description,String enc)	The property list and the string specified by description is written to the XML document linked to streamOut using the specified character encoding.
Set<String> stringPropertyNames( )	Returns a set of keys.

Example 3.8:

The following example demonstrates Properties. It creates a property list in which the keys are the names of states and the values are the names of their capitals. Notice that the attempt to find the capital for Florida includes a default value.

// Demonstrate a Property list.

import java.util.*;

class PropDemo {

public static void main(String args[]) {

Properties capitals = new Properties();

capitals.put("Illinois", "Springfield");

capitals.put("Missouri", "Jefferson City");

capitals.put("Washington", "Olympia");

capitals.put("California", "Sacramento");

capitals.put("Indiana", "Indianapolis");

// Get a set-view of the keys.

Set<?> states = capitals.keySet();

// Show all of the states and capitals.

for(Object name : states)

System.out.println("The capital of " +

name + " is " +

capitals.getProperty((String)name)

+ ".");

System.out.println();

// Look for state not in list -- specify default.

String str = capitals.getProperty("Florida", "Not Found");

System.out.println("The capital of Florida is " + str + ".");

}

The output from this program is shown here:

The capital of Missouri is Jefferson City.

The capital of Illinois is Springfield.

The capital of Indiana is Indianapolis.

The capital of California is Sacramento.

The capital of Washington is Olympia.

The capital of Florida is Not Found.

Since Florida is not in the list, the default value is used.

Example 3.9:

Although it is perfectly valid to use a default value when you call getProperty( ), as the preceding example shows, there is a better way of handling default values for most applications of property lists. For greater flexibility, specify a default property list when constructing a Properties object. The default list will be searched if the desired key is not found in the main list. For example, the following is a slightly reworked version of the preceding program, with a default list of states specified. Now, when Florida is sought, it will be found in the default list:

// Use a default property list.

import java.util.*;

class PropDemoDef {

public static void main(String args[]) {

Properties defList = new Properties();

defList.put("Florida", "Tallahassee");

defList.put("Wisconsin", "Madison");

Properties capitals = new Properties(defList);

capitals.put("Illinois", "Springfield");

capitals.put("Missouri", "Jefferson City");

capitals.put("Washington", "Olympia");

capitals.put("California", "Sacramento");

capitals.put("Indiana", "Indianapolis");

// Get a set-view of the keys.

Set<?> states = capitals.keySet();

// Show all of the states and capitals.

for(Object name : states)

System.out.println("The capital of " +

name + " is " +

capitals.getProperty((String)name)

+ ".");

System.out.println();

// Florida will now be found in the default list.

String str = capitals.getProperty("Florida");

System.out.println("The capital of Florida is "

+ str + ".");

}

Using store( ) and load( )

One of the most useful aspects of Properties is that the information contained in a Properties object can be easily stored to or loaded from disk with the store( ) and load( ) methods.
At any time, you can write a Properties object to a stream or read it back. This makes property lists especially convenient for implementing simple databases.

The following program uses a property list to create a simple computerized telephone book that stores names and phone numbers. To find a person’s number, you enter his or her name. The program uses the store( ) and load( ) methods to store and retrieve the list. When the program executes, it first tries to load the list from a file called phonebook.dat. If this file exists, the list is loaded. You can then add to the list. If you do, the new list is saved when you terminate the program. Notice how little code is required to implement a small, but functional, computerized phone book.

Example 3.10:

A simple telephone number database that uses a property list.

import java.io.*;

import java.util.*;

class Phonebook {

public static void main(String args[]) throws IOException{

Properties ht = new Properties();

BufferedReader br =

new BufferedReader(new InputStreamReader(System.in));

String name, number;

FileInputStream fin = null;

boolean changed = false;

// Try to open phonebook.dat file.

try {

fin = new FileInputStream("phonebook.dat");

} catch(FileNotFoundException e) {

// ignore missing file

}

/* If phonebook file already exists,

load existing telephone numbers. */

try {

if(fin != null) {

ht.load(fin);

fin.close();

}

} catch(IOException e) {

System.out.println("Error reading file.");

}

// Let user enter new names and numbers.

do {

System.out.println("Enter new name" +

" ('quit' to stop): ");

name = br.readLine();

if(name.equals("quit")) continue;

System.out.println("Enter number: ");

number = br.readLine();

ht.put(name, number);

changed = true;

} while(!name.equals("quit"));

// If phone book data has changed, save it.

if(changed) {

FileOutputStream fout = new FileOutputStream("phonebook.dat");

ht.store(fout, "Telephone Book");

fout.close();

}

// Look up numbers given a name.

do {

System.out.println("Enter name to find" +

" ('quit' to quit): ");

name = br.readLine();

if(name.equals("quit")) continue;

number = (String) ht.get(name);

System.out.println(number);

} while(!name.equals("quit"));

}